1. Field of the Invention
The invention relates to a variable length coder (also known as "Huffman coder", or "entropy" for use in digital audio/video coders and the like.
2. Related Art of the Invention
In many digital video coders a lossy coding algorithm based on the discrete cosine transform (DCT) precedes a lossless encoder based on variable length coding (VLC).
The transform coefficients are run-levelled and entropy coded, in which the most common run-level combinations are given the shortest codes and the less common combinations longer codes. A run-level represents a group of 1 or more transform coefficients as a number of 0 coefficients (run) followed by a single coefficient value (level). One example of run-level combination to codes is disclosed in Tables 1 to 4. For example, H.261 (see "Recommendation H.261--Video Codec for Audio-visual Services at p.times.64 kbits/s" by International Telegraph and Telephone Consultative Committee, Study Group XV, CCITT Subgroup XV Document, Report R 37, August 1990) and MPEG-1 (see "CD 11172--Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbps" by international Organization for Standardization, ISO MPEG Document, ISO-IEC/JTC1/SC2/WG8, 1992) describe audio/video codecs which require variable length coders. Emerging standard HDTV codecs will also require variable length coders.
The implementation of a variable length coder has typically been accomplished by the use of a look-up table (LUT) to translate the fixed length data to variable length data. The LUT is usually implemented using memory (for example RAM or PROM), or logic (for example PLA). Lei and Sun (see "An Entropy Coding System for Digital HDTV Applications", Shaw-Min Lei & Ming-Ting Sun, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 1, March 1991) implemented a LUT using a PLA. The PLA contains the codeword bitsequence and the length of the bitsequence. The input to the PLA is the fixed length data from a run-leveller, and the output is the codeword bitsequence and the length of the bitsequence. Vogel (see "Method and Apparatus for Bit Rate Reduction", Peter Vogel, U.S. Pat. No. 4,901,075, Feb. 13, 1990) described an implementation which used a PROM to implement a LUT. The run-level fixed length data was applied directly to the address bus of the PROM, and the representation of the variable length bitsequence is output on the data bus. However, there are several problems which this invention solves. Due to the rapidly changing digital A/V coding technology, and also due to the wide range of applications, the contents of the huffman tables used for variable length coding may change. This results in a need for programmable variable length codetables. Contrary to programmability is the need for small implementation size so that inexpensive VLSI codecs can be made. An object of this invention is to implement a small, programmable architecture for variable length coding.
In MPEG-1 and H.261, the huffman tables are not continuous. Not every run-level combination exists, and of the combinations which do exist, they are not necessarily contiguous. For example, a codeword for run=6, level=0, 1, 2, & 3 exists, but not for run=6, level=4, nor for run=7, level=3. This means that an implementation using conventional memory will have "holes" of unused memory, portions of memory which contain no useful information because the run-level combination has no codeword. This is a waste of VLSI chip space. Alternatively, a PLA can be used but PLAs have more limited versatility than RAM. An object of this invention is to eliminate the wastage of codetable space by the occurrence of holes in the huffman tables. Quite often the huffman tables contain patterns in the variable length bit sequences which can be identified and used to shrink the codetable.
For example, in MPEG-1 the longest bitsequence in the DCT coefficients huffman table is 16 bits (disregarding the sign of the level). However, all of the longer bitsequence consist of a string of 0s, followed by several 1s. This pattern can be recognized and used to reduce the codetable size. An object of this invention is to eliminate the wastage of codetable space caused by storing redundant information in the codetable.